FIG. 1 shows the structure of a crossbar matrix 1 in which input lines 10 and output lines 20 are shown to be situated perpendicular to each other and are further shown to be connected at respective crosspoints. The crossbar matrix 1 is non-blocking—any input line may be connected to any output line without blocking other input-to-output connections. For a N×N square crossbar wherein the number of input lines and output lines are the same, (N representing the number of input lines and the number of output lines) the complexity grows by N2. In addition to complexity in monolithic IC implementation, the package pin constraints will limit the number of input and output lines (N).
Multi-stage Interconnection Networks (MIN) enable building large switches from smaller switches in a structured manner. A three stage (stages 120, 130 and 140) network is shown in FIG. 2. The network of FIG. 2 is a class of networks based on the Clos network. This type of network belongs to so-called constant stage networks or limited stage networks. In FIG. 2, a Clos network 100 is shown with N input lines 110 and N output lines 150. The N input lines 110 are divided into m groups 111, 112, . . . , 119, in FIG. 2 we are showing ‘n’ rather than ‘m’, each group consisting of n inputs (N=m*n). Each group of n inputs is connected to a (n×k) switch 121, 122, . . . 129. The first stage 120 (also called input stage) consists of m groups of (n×k) switches 121, 122, . . . , 129, each having n input lines (not shown) and k output lines (not shown). The second stage 130 (also called middle stage) consists of k switches 131, 132, . . . , 139 of size (m×m). The third stage 140 (also called the output stage) consists of m(k×n) switches 141, . . . , 149. The N output lines 150 include the outputs 151, 152, . . . , 159 of the m switches 141, 142, . . . , 149, respectively, in the output stage 140.
With reference to FIG. 2, the outputs 161, 162, . . . , 169 of the first stage 120 each consist of k lines which will be denoted by O1ij (1≦i≦m, 1≦j≦k), the i index identifies the switch in the 1st stage and the index j identifies one of the k output lines of the 1st stage of the switch. The input lines 171, 172, . . . 179 of the second stage 130 each consist of m lines denoted by I2ij (1≦i≦k, 1≦j≦m) the index i identifies one of the k switches and the index j identifies one of the m input lines of the switch. The output lines 181, 182, . . . 189 of the second stage 130 each consist of m lines denoted by O2ij (1≦i≦k, 1≦j≦m) the index i identifies one of the k switches and the index j identifies one of the m output lines. The input lines 191, 192, . . . 199 of the third stage 140 each consist of k lines denoted by I3ij (1≦i≦m, 1≦j≦k) the index i identifies one of the m switches and the index j identifies one of the k input lines of the switch. The output lines 151, 152, . . . 159 of the third stage 140 each consist of n lines denoted by O3ij (1≦i≦m, 1≦j≦n) the index i identifies one of the m switches and the index j identifies one of the n outputs of the switch. The interconnection between stages is as follows:                Output j of switch i in the first stage (O1ij) is connected to input i of switch j in the second stage (I2ji).        Output j of switch i in the second stage (O2ij) is connected to input i of switch j in the third stage (I3ji).        
The Clos network 100 of FIG. 2 is denoted as a v(k, n, m). To avoid blocking problems, the design parameters of the network must be selected properly. Clos has shown that the three stage network of FIG. 2 is strictly non-blocking if k≧(2n−1). The complexity of switch can be reduced if existing connections can be broken and remade without loss of data in order to establish additional new connections. This type of switch is called a Rearrangeably Nonblocking Switch. The three stage network of FIG. 2 is rearrangeably nonblocking if k≧n.
The input stage 120 and output stages 140 of a Clos network consist of m switches. The middle stage 130 of network 100 consists of k switches. The prior art suggest systems with integrated input and output stages and separate middle stage. The problem with prior art is that the structure is not modular, that is the v(k, n, m) network of FIG. 2 can not be constructed from m identical modules.
Therefore, there is a need for constructing a Clos network v(k, n, m) from m identical modules, furthermore there is a need for constructing a modular and scalable Clos networks v(k, n, m), wherein network of different sizes (different values of m) can be constructed from m identical modules and allows building larger networks from a module by adding such modules as needed. The advantage of a modular structure is that it allows integration into a single module or monolithic Integrated Circuit (IC). The advantages of modular and scalable structure is that it allows building networks of different sizes from the same module or IC.